package com.example.leetcode.trainingcamp.week6.Thursday;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
 */
public class Offer32_III {

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> result = new ArrayList<>();
        int height = 1;
        queue.add(root);
        while (queue.size() != 0){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            if (height % 2 == 1){
                for (int i =size-1;i>=0;i--){
                    TreeNode poll = queue.remove(i);
                    if (poll.left != null){
                        queue.add(poll.left);
                    }
                    if (poll.right != null){
                        queue.add(poll.right);
                    }
                    list.add(poll.val);
                }
            }else {
                for (int i = size-1;i>=0;i--){
                    TreeNode poll = queue.remove(i);
                    if (poll.right != null){
                        queue.add(poll.right);
                    }
                    if (poll.left != null){
                        queue.add(poll.left);
                    }
                    list.add(poll.val);
                }
            }
            height++;
            result.add(list);
        }
        return result;
    }
}
